def agPalindr(s):
	n=len(s)
	m=[[0 for x in range(n+1)] for y in range(n+1)]
	for ini in range(2,n+1):
		j,i=ini,0
		while j<=n:
			if s[i]==s[j-1]: m[i][j]=m[i+1][j-1]
			else: m[i][j]=min(m[i][j-1],m[i+1][j])+1
			j+=1
			i+=1
	print '\n'.join(map(lambda x:' '.join(map(str,x)),m))
	return m[0][n]

f=open('palindromo.in')
while f.readline().rstrip()!="0":
	print agPalindr(f.readline().rstrip())
